#include <iostream>
#include <vector>
using namespace std;

vector<vector<string> > res;
bool isValid(vector<string> &board, int row, int col)
{
    //主要判断board[row][col]的位置和当前列和左上方，右上方是否有冲突
    int n = board.size();
    //检查是否有列冲突检查board[0][col],board[1][col],...
    for(int i = 0; i < row; i++)
    {
        if(board[i][col] == 'Q')
            return false;
    }
    //检查左上方是否有冲突即board[row-1][col-1]的位置是否有皇后
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
    {
        if (board[i][j] == 'Q')
            return false;
    }
    //检查右上方是否有冲突，是要检查右上方这整条斜线上，而不仅仅是右上方的一个点
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
    {
        if (board[i][j] == 'Q')
            return false;
    }
    return true;

}

void backtrack(vector<string> &board, int row)  //board.size()就是棋盘的总行数
{
    //放置皇后：从第一行，到第二行，一直到最后一行，每行选择一个位置放置皇后。row记录的是当前选择的行数
    //小于row的行数都已经放置好了皇后。
    //路径：棋盘中小于row行的那些行都已经放置了皇后
    //选择列表：第row行中的每一列都是可以选择的。
    //结束条件：row超过board的总行数
    if (board.size() == row)  //注意row是从0开始增长的。
    {
        vector<string> temp(board);
        res.push_back(temp);
        return;
    }
    for(int i = 0; i < board.size(); i++)
    {   
        //排除不合法的。
        if(!isValid(board, row, i))
            continue;

        //做选择
        board[row][i] = 'Q';
        //回调回溯函数
        backtrack(board, row + 1);
        //撤销选择
        board[row][i] = '.';

    }
}
int main()
{
    using namespace std;

    int n = 8; 
    vector<string> board(n, string(n, '.'));
    backtrack(board, 0);  //从第0行开始
    cout << n << "皇后的解法：" << res.size() << endl;
    /*
    for(unsigned int i = 0; i < res.size(); i++)
    {
        for(unsigned int j = 0; j < res[i].size(); j++)
        {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }
    */
    return 0;
}